import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Leetcode494 {
    Map<String, Integer> map = new HashMap<>();
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums,target,0,0);
    }

    public int dfs(int[] nums, int target,int start ,int curr){
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            String next = scanner.next();

        }
        if (start==nums.length){
            return curr == target?1:0;
        }
        String key = start+"_"+curr;
        if (map.containsKey(key)){
            return map.get(key);
        }
        int left = dfs(nums, target, start + 1, curr + nums[start]);
        int right = dfs(nums, target, start + 1, curr - nums[start]);
        map.put(key,right+left);
        return map.get(key);
    }
}
